package main

import (
	"fmt"
	"strings"
)

/**
 * @param generator: Generating set of rules.
 * @param startSymbol: Start symbol.
 * @param symbolString: Symbol string.
 * @return: Return true if the symbol string can be generated, otherwise return false.
 */
func CanBeGenerated(generator []string, startSymbol byte, symbolString string) bool {
	//图
	g := map[string][]string{}
	for _, v := range generator {
		slice := strings.Split(v, " -> ")
		key := string(slice[0][0])
		value := slice[1]

		_, ok := g[key]
		if !ok {
			g[key] = []string{}
		}

		g[key] = append(g[key], value)
	}
	return f1(string(startSymbol), symbolString, g)
}

// 图是深度优先
func f1(cur, end string, g map[string][]string) bool {
	if cur == end {
		return true
	}

	if len(cur) > len(end) {
		return false
	}

	nexts := getnexts(cur, g)

	for _, s := range nexts {
		if f1(s, end, g) {
			return true
		}
	}

	return false
}

func getnexts(cur string, g map[string][]string) []string {
	ans := []string{}
	for i := 0; i < len(cur); i++ {
		key := string(cur[i])

		arr, ok := g[key]
		if ok {
			for _, item := range arr {
				ans = append(ans, cur[0:i]+item+cur[i+1:])
			}
		}
	}
	return ans
}

func main() {
	fmt.Println(
		CanBeGenerated([]string{"S -> abc", "S -> aA", "A -> b", "A -> c"},
			'S', "abc")) //true
	fmt.Println(
		CanBeGenerated([]string{"S -> abc", "S -> aA", "A -> b", "A -> c"},
			'S', "ac")) //true
	fmt.Println(
		CanBeGenerated([]string{"S -> abcd", "S -> A", "A -> abc"},
			'S', "abc")) //true

	fmt.Println(
		CanBeGenerated([]string{"S -> abc", "S -> aA", "A -> b", "A -> c"},
			'S', "a")) //false
	str := "one,two,three,four,five"
	// 使用逗号作为分隔符
	slice := strings.Split(str, ",")
	fmt.Println(slice) // 输出: [one two three four five]
}

/*
["S -> abc", "S -> aA", "A -> b", "A -> c"]
S
"abc"
输出数据
false
期望答案
true
*/
